package dataStructures;

import java.util.Iterator;

/**
 * Created with IntelliJ IDEA.
 * User: Vikas.Bhardwaj
 * Date: 5/22/12
 * Time: 2:45 PM
 * To change this template use File | Settings | File Templates.
 */
public class LinkedList<T extends Comparable<? super T>> implements Iterable{

    LinkedListNode<T> root;

    public LinkedList(T value) {
        LinkedListNode<T> node = new LinkedListNode<T>(value);
        this.root = node;
    }

    public LinkedList(LinkedListNode<T> root) {
        this.root = root;
    }

    /**
     * Removes the first occurrence of the value
     * @param value
     * @return position from root where the removal took place
     */
    public int removeNode(T value){
        int result = -1;
        LinkedListNode<T> currentNode = root;


        if(root.getValue().equals(value)){
            root = root.getNext();
            result = 0;
        }
        int c = 0;
        while(currentNode.getNext()!=null && result == -1){
            c++;
            if(currentNode.getNext().getValue().equals(value)){
                // remove this node
                currentNode.setNext(currentNode.getNext().getNext());
                result = c;
            }else currentNode = currentNode.getNext();
        }
        return result;
    }

    public int insertNode(T value){
        LinkedListNode<T> currentNode = root;
        int c = 0;
        while(currentNode.getNext()!=null){
            currentNode = currentNode.getNext();
            c++;
        }

        LinkedListNode<T> newNode = new LinkedListNode<T>(value);
        currentNode.setNext(newNode);

        return c;
    }

    public void insertNodes(T[] values){
        for (T value : values) {
            insertNode(value);
        }
    }

    public LinkedList<T> reverseLinkedList(){

        LinkedListNode<T> previous = null;
        LinkedListNode<T> lastNode = null;
        LinkedListNode<T> currentNode = root;

        while(currentNode!=null){
            lastNode = currentNode.getNext();
            currentNode.setNext(previous);

            previous = currentNode;
            currentNode = lastNode;
        }
        return new LinkedList<T>(previous);
    }

    public void printLinkedList(){
        LinkedListNode<T> currentNode = root;

        while(currentNode!=null){
            System.out.print(currentNode.getValue() + " ");
            currentNode = currentNode.getNext();
        }
        System.out.println("--");
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {

            LinkedListNode<T> currentNode = root;
            @Override
            public boolean hasNext() {
                return currentNode.getNext()!=null;
            }

            @Override
            public T next() {
                currentNode = currentNode.getNext();
                return currentNode.getValue();
            }

            @Override
            public void remove() {
                //removes the head node
                root = root.getNext();
            }
        };
    }

    class LinkedListNode<T extends Comparable<? super T>>{
        T value;
        LinkedListNode<T> next;

        LinkedListNode(T value) {
            this.value = value;
        }

        public T getValue() {
            return value;
        }

        public void setValue(T value) {
            this.value = value;
        }

        public LinkedListNode<T> getNext() {
            return next;
        }

        public void setNext(LinkedListNode<T> next) {
            this.next = next;
        }
    }

    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<Integer>(10);

        linkedList.insertNodes(new Integer[]{5, 10, 6, 3, 4, 1, 6});
        linkedList.printLinkedList();
        LinkedList<Integer> reversedLinkedList = linkedList.reverseLinkedList();
        reversedLinkedList.printLinkedList();

    }
}
